#include <iostream>
#include <algorithm>
#include <vector>
//快速排序，和冒泡排序有点类似，不过冒泡每次找到最大的数值丢后面，而快速排序每次找中间
//的某个值，其左边的数小于中间值pivot，其右边值大于pivot，然后递归排序
//其实也和归并排序有点类似,
// 42 10 23 34 96 78 60 14
//实现体
void quickSort1(std::vector<int> &arr, int left, int right)
{
	if (left >= right)
	{
		return ;
	}
	int i = left, j = right;
	int pivot = arr[i];
	
	while (i < j)
	{
		while (i<j && arr[j] >= pivot)
		{
			--j;
		}
		arr[i] = arr[j];
		while (i<j && arr[i] <= pivot)
		{
			++i;
		}
		arr[j] = arr[i];
	}
	//i==j
	arr[i] = pivot;
	quickSort1(arr, left, i - 1);
	quickSort1(arr, i + 1, right);

}

//实现体
//稍微改改能适用于单链表排序
// 42 10 23 34 96 78 60 14
void quickSort2(std::vector<int> &arr, int left, int right)
{
	if (left >= right)
	{
		return ;
	}
	int pivot = arr[left];
	int i = left + 1;
	int j = left + 1;
	while (j <= right)
	{
		if (arr[j] < pivot)
		{
			std::swap(arr[j], arr[i]);
			++i;
		}
		++j;
	}
	//最后i指向大于等于pivot的位置
	std::swap(arr[left], arr[i - 1]);
	quickSort2(arr, left, i - 2);
	quickSort2(arr, i, right);
	
}


void quickSort1(std::vector<int> &arr)
{
	int n = arr.size();
	
	quickSort1(arr, 0, n - 1);
}

//稍微改改能适用于单链表排序
void quickSort2(std::vector<int> &arr)
{
	int n = arr.size();
	
	quickSort2(arr, 0, n - 1);
}
int main()
{
	std::vector<int> arr{3,4,5,3,1,7,8,7,0,13,22,4,1,2,6,7382,33,2231,312312,4341,3131,1231241,1231232,122,3213,132312,3124,5754,7765,32423,4654,234234,23342,345,757,87,980};
	std::vector<int> b;
	b.assign(arr.begin(), arr.end());
	quickSort2(arr);
	for (auto i : arr)
	{
	std::cout << i << std::endl;
	}
	std::sort(b.begin(), b.end());
	if (b != arr)
	{
		std::cout << "sort failure!!" << std::endl;
	}
	else
	{
		std::cout << "sort success!!!!" << std::endl;
	}

	return 0;
}